<?php
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class Solution {
    // 前序
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function preorderTraversal($root)
    {
        if ($root == null) {
            return array();
        }
        return $this->preorderHelper($root, array());
    }

    function preorderHelper($node, $node_list)
    {
        array_push($node_list, $node->val);

        if ($node->left) {
            $node_list = $this->preorderHelper($node->left, $node_list);
        }

        if ($node->right) {
            $node_list = $this->preorderHelper($node->right, $node_list);
        }

        return $node_list;
    }

    // 中序
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root)
    {
        if ($root == null) {
            return array();
        }
        return $this->inorderHelper($root, array());
    }

    function inorderHelper($node, $node_list)
    {
        if ($node->left) {
            $node_list = $this->inorderHelper($node->left, $node_list);
        }
        array_push($node_list, $node->val);
        if ($node->right) {
            $node_list = $this->inorderHelper($node->right, $node_list);
        }
        return $node_list;
    }

    // 后序
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root)
    {
        if ($root == null) {
            return array();
        }
        return $this->postorderHelper($root, array());
    }

    function postorderHelper($node, $node_list)
    {
        if ($node->left) {
            $node_list = $this->postorderHelper($node->left, $node_list);
        }

        if ($node->right) {
            $node_list = $this->postorderHelper($node->right, $node_list);
        }

        array_push($node_list, $node->val);

        return $node_list;
    }

    // 层序
    function levelOrder($root) {
        if ($root == null) {
            return array();
        }
        $queue = array();
        array_push($queue, $root);
        $data = array();
        while (!empty($queue)) {
            $len = count($queue);
            $level_data = array();
            for ($index=0; $index<$len; $index++) {
                $node = $queue[$index];
                unset($queue[$index]);
                $level_data[] = $node->val;
                if ($node->left) {
                    array_push($queue, $node->left);
                }
                if ($node->right) {
                    array_push($queue, $node->right);
                }
            }
            $data[] = $level_data;
            $queue = array_values($queue);
        }
        return $data;
    }

    /*public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        robot(root, ans, 0);
        return ans;
    }

    private void robot(TreeNode root, List<List<Integer>> ans, int level) {
        if (root == null) {
            return;
        }
        if (ans.size() == level) {
            ans.add(new ArrayList());
        }
        ans.get(level).add(root.val);
        robot(root.left, ans, level + 1);
        robot(root.right, ans, level + 1);
    }*/

}